"""
Answe inspired by the post from here: 
https://leetcode.com/problems/house-robber-iii/discuss/79330/Step-by-step-tackling-of-the-problem
"""

class 树节点:
    def __init__(self, 值=0, 左=None, 右=None):
        self.值 = 值
        self.左 = 左
        self.右 = 右

class Solution:
    # 贪婪
    def 盗亦有道(self, 根):
        def 寻(根):
            if not 根: return [0, 0]
            左, 右 = 寻(根.左), 寻(根.右)
            放过 = max(左) + max(右)
            打劫 = 根.值 + 左[0] + 右[0]
            return [放过, 打劫]
        return max(寻(根))

case1 = 树节点(3, 
                 左 = 树节点(2, None, 树节点(3)),
                 右 = 树节点(3, None, 树节点(1)))
case2 = 树节点(3,
                 左 = 树节点(4, 树节点(1), 树节点(3)),
                 右 = 树节点(5, None, 树节点(1)))
s = Solution()
print(s.盗亦有道(case1))
print(s.盗亦有道(case2))